#include <bits/stdc++.h>
using namespace std;

/*
966. 元音拼写检查器
已解答
中等
相关标签
premium lock icon
相关企业
在给定单词列表 wordlist 的情况下，我们希望实现一个拼写检查器，将查询单词转换为正确的单词。

对于给定的查询单词 query，拼写检查器将会处理两类拼写错误：

大小写：如果查询匹配单词列表中的某个单词（不区分大小写），则返回的正确单词与单词列表中的大小写相同。
例如：wordlist = ["yellow"], query = "YellOw": correct = "yellow"
例如：wordlist = ["Yellow"], query = "yellow": correct = "Yellow"
例如：wordlist = ["yellow"], query = "yellow": correct = "yellow"
元音错误：如果在将查询单词中的元音 ('a', 'e', 'i', 'o', 'u')  分别替换为任何元音后，能与单词列表中的单词匹配（不区分大小写），则返回的正确单词与单词列表中的匹配项大小写相同。
例如：wordlist = ["YellOw"], query = "yollow": correct = "YellOw"
例如：wordlist = ["YellOw"], query = "yeellow": correct = "" （无匹配项）
例如：wordlist = ["YellOw"], query = "yllw": correct = "" （无匹配项）
此外，拼写检查器还按照以下优先级规则操作：

当查询完全匹配单词列表中的某个单词（区分大小写）时，应返回相同的单词。
当查询匹配到大小写问题的单词时，您应该返回单词列表中的第一个这样的匹配项。
当查询匹配到元音错误的单词时，您应该返回单词列表中的第一个这样的匹配项。
如果该查询在单词列表中没有匹配项，则应返回空字符串。
给出一些查询 queries，返回一个单词列表 answer，其中 answer[i] 是由查询 query = queries[i] 得到的正确单词。

 

示例 1：

输入：wordlist = ["KiTe","kite","hare","Hare"], queries = ["kite","Kite","KiTe","Hare","HARE","Hear","hear","keti","keet","keto"]
输出：["kite","KiTe","KiTe","Hare","hare","","","KiTe","","KiTe"]
示例 2:

输入：wordlist = ["yellow"], queries = ["YellOw"]
输出：["yellow"]
 

提示：

1 <= wordlist.length, queries.length <= 5000
1 <= wordlist[i].length, queries[i].length <= 7
wordlist[i] 和 queries[i] 只包含英文字母
*/

// 法一
class Solution {
private: 
    // 辅助函数：将字符串转换为小写，修复字符处理问题
    string toLower(string& s) {
        string res = s;  // 创建副本避免修改原字符串
        for (char& c : res) {
            // 安全转换为小写，处理所有ASCII字符
            c = tolower(static_cast<unsigned char>(c));
        }
        return res;
    }

    // 辅助函数：将元音替换为*，确保统一处理
    string replaceVowels(string s) {
        s = toLower(s);
        for (char& c : s) {
            // 明确匹配所有元音字母
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                c = '*';
            }
        }
        return s;
    }

public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        // 存储完全匹配的单词（区分大小写）
        unordered_set<string> exactMatches;
        // 存储大小写不敏感的匹配（键为小写单词，值为第一个出现的原始单词）
        unordered_map<string, string> caseInsensitive;
        // 存储元音不敏感的匹配（键为替换元音后的小写单词，值为第一个出现的原始单词）
        unordered_map<string, string> vowelInsensitive;

        // 构建三个映射，确保保留第一个出现的单词
        for (string& word : wordlist) {
            // 完全匹配集合
            exactMatches.insert(word);
            
            // 大小写映射（只保留第一个出现的单词）
            string lowerWord = toLower(word);
            // 只有当键不存在时才添加，确保保留第一个出现的单词
            if (caseInsensitive.find(lowerWord) == caseInsensitive.end()) {
                caseInsensitive[lowerWord] = word;
            }
            
            // 元音映射（只保留第一个出现的单词）
            string vowelWord = replaceVowels(word);
            // 只有当键不存在时才添加，确保保留第一个出现的单词
            if (vowelInsensitive.find(vowelWord) == vowelInsensitive.end()) {
                vowelInsensitive[vowelWord] = word;
            }
        }

        // 处理每个查询
        vector<string> result;
        for (string& query : queries) {
            // 优先级1：完全匹配（区分大小写）
            if (exactMatches.count(query)) {
                result.push_back(query);
                continue;
            }
            
            // 优先级2：大小写不敏感匹配
            string lowerQuery = toLower(query);
            if (caseInsensitive.find(lowerQuery) != caseInsensitive.end()) {
                result.push_back(caseInsensitive[lowerQuery]);
                continue;
            }
            
            // 优先级3：元音不敏感匹配
            string vowelQuery = replaceVowels(query);
            if (vowelInsensitive.find(vowelQuery) != vowelInsensitive.end()) {
                result.push_back(vowelInsensitive[vowelQuery]);
                continue;
            }
            
            // 无匹配项
            result.push_back("");
        }
        return result;
    }
};

// 法二
class Solution {
    // 辅助：将字符串转为全小写，为大小写不敏感匹配做准备
    string tolower_string(string s) {
        for (char& c : s) c = tolower(c);
        return s;
    }

    // 辅助：将【小写字符串】的元音替换为'?'（统一元音匹配标记），输入已确保小写
    string replace_vowels(string s) {
        for (char& c : s) {
            if (c == 'a' || c == 'e' || c == 'i' || c == 'o' || c == 'u') {
                c = '?';
            }
        }
        return s;
    }

public:
    vector<string> spellchecker(vector<string>& wordlist, vector<string>& queries) {
        int n = wordlist.size();
        // origin：存原始单词，用于O(1)判断完全匹配（区分大小写）
        unordered_set<string> origin(wordlist.begin(), wordlist.end());
        // lower_to_origin：小写单词→原始单词，处理大小写错误匹配
        unordered_map<string, string> lower_to_origin;
        // vowel_to_origin：元音替换后的小写单词→原始单词，处理元音错误匹配
        unordered_map<string, string> vowel_to_origin;

        // 倒序遍历单词列表：后期遍历的「早期单词」会覆盖「后期单词」，确保保留第一个出现的原始单词（符合优先级）
        for (int i = n - 1; i >= 0; i--) {
            string& s = wordlist[i];
            string lower = tolower_string(s);
            lower_to_origin[lower] = s; // 更新小写→原始映射（早期单词覆盖）
            vowel_to_origin[replace_vowels(lower)] = s; // 更新元音替换→原始映射（先转小写再替换）
        }

        // 直接修改查询数组（减少额外空间开销），按优先级处理每个查询
        for (string& q : queries) {
            // 优先级1：完全匹配（区分大小写），存在则无需修改
            if (origin.contains(q)) continue;
            
            string lower_q = tolower_string(q);
            // 优先级2：大小写不敏感匹配，找到则用原始单词替换
            auto lower_it = lower_to_origin.find(lower_q);
            if (lower_it != lower_to_origin.end()) {
                q = lower_it->second;
            } 
            // 优先级3：元音不敏感匹配，找到则赋值，否则设为空
            else {
                auto vowel_it = vowel_to_origin.find(replace_vowels(lower_q));
                q = vowel_it != vowel_to_origin.end() ? vowel_it->second : "";
            }
        }

        return queries;
    }
};